package year2023.greedy;

import java.util.Comparator;
import java.util.PriorityQueue;

public class Code04_IPO {

    /*
    * 输入:正数数组costs,正数数组profits,正数K,正数M
    *
    * costs[i] 表示i号项目的花费
    * profits[i] 表示i号项目在扣除花费的利润
    * K表示你只能串行的最多做K个项目
    * M表示你初始的资金
    * 说明:每做完一个项目，马上获得的收益，可以支持你去做下一个项目，不能并行做项目
    * 输出:你最后获得的最大钱数。
    * */

    //最多K个项目
    //初始资金W
    // Profits[] 利润 Capital[] 花费  他俩数组一定等长
    //返回最终最大的资金
    public static int findMaximizedCapital(int K, int W, int[] Profits, int[] Capital){

        PriorityQueue<Program> minCostQ = new PriorityQueue<>(new MinCostComparator());

        PriorityQueue<Program> maxProfitQ = new PriorityQueue<>(new MaxProfitComparator());

        for (int i = 0; i < Profits.length; i++) {
            minCostQ.add(new Program(Profits[i], Capital[i]));
        }
        for (int i = 0; i < K; i++) {
            while (!minCostQ.isEmpty() && minCostQ.peek().c <= W){
                maxProfitQ.add(minCostQ.poll());
            }
            if (maxProfitQ.isEmpty()){
                return W;
            }
            W += maxProfitQ.poll().p;
        }
        return W;

    }

    public static class Program{
        public int p;
        public int c;

        public Program(int p, int c){
            this.p = p;
            this.c = c;
        }
    }

    public static class MinCostComparator implements Comparator<Program>{

        @Override//小到大
        public int compare(Program o1, Program o2){
            return o1.c - o2.c;
        }
    }

    public static class MaxProfitComparator implements Comparator<Program>{

        @Override//大到小
        public int compare(Program o1, Program o2){
            return o2.p - o1.p;
        }
    }


}
